package util;

public class Heap {
	public static int parent(int index)
	{
		if(index > 0)
		{
			return (index - 1) / 2;
		}
		else
		{
			return -1;
		}
	}
	
	public static int left(int index)
	{                                                                                                        
		return index * 2 + 1;
	}
	
	public static int right(int index)
	{
		return index * 2 + 2;
	}
	
	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void minHeapify(Comparable[] comparable, int i, int heapSize)
	{
		int smallest;
		
		int l = left(i);
		if(l < heapSize && comparable[l].compareTo(comparable[i]) < 0)
			smallest = l;
		else
			smallest = i;
		
		int r = right(i);
		if(r < heapSize && comparable[r].compareTo(comparable[smallest]) < 0)
			smallest = r;
			
		if(smallest != i)
		{
			ArrayUtil.each(comparable, smallest, i);
			minHeapify(comparable, smallest, heapSize);
		}
	}

	@SuppressWarnings({ "rawtypes"})
	public static void buildMinHeap(Comparable[] comparables, int heapSize)
	{
		for(int i = parent(comparables.length - 1); i >= 0; i --)
		{
			minHeapify(comparables, i, heapSize);
		}
	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void maxHeapify(Comparable[] comparables, int i, int heapSize)
	{
		int largest;
		int l = left(i);
		if(l < heapSize && comparables[l].compareTo(comparables[i]) > 0)
			largest = l;
		else
			largest = i;
		
		int r = right(i);
		if(r < heapSize && comparables[r].compareTo(comparables[largest]) > 0)
			largest = r;
		
		if(largest != i)
		{
			ArrayUtil.each(comparables, largest, i);
			maxHeapify(comparables, largest, heapSize);
		}
	}

	@SuppressWarnings({ "rawtypes"})
	public static void buildMaxHeap(Comparable[] comparables, int heapSize)
	{
		for(int i = parent(comparables.length - 1); i >= 0; i --)
		{
			maxHeapify(comparables, i, heapSize);
		}
	}
}
